package Subject;

public class Candy {

/**
 * 难度：困难
 * 
 * 135. 分发糖果
 * 	老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
 * 	你需要按照以下要求，帮助老师给这些孩子分发糖果：
 * 		每个孩子至少分配到 1 个糖果。
 * 		相邻的孩子中，评分高的孩子必须获得更多的糖果。
 * 	那么这样下来，老师至少需要准备多少颗糖果呢？
 * 
 * 示例 1:
 * 	输入: [1,0,2]
 * 	输出: 5
 * 	解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
 * 
 * 示例 2:
 * 	输入: [1,2,2]
 * 	输出: 4
 * 	解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
 * 	     第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Candy candy = new Candy();
		int[] i= {1,2,87,87,87,2,1};
		System.out.println(candy.candy1(i));
	}
	
	//自己写
	/**
	 * 执行用时：1439 ms, 在所有 Java 提交中击败了5.37%的用户
	 * 内存消耗：39.9 MB, 在所有 Java 提交中击败了21.64%的用户
	 * */
	public int candy1(int[] ratings) {
		//查看数组长度
		//每个数跟后一位数比较，如果比后面数大（则后一位的糖果数量=当前位的糖果数量+1），
		//前面比后面数小（则遍历前面的位数，比前面数大的糖果数都递增1），一样则等于0
		//最后把所有糖果加起来+人数
		int n=ratings.length;
		//存储对应ratings的位数的糖果数量
		int[] a=new int[n];
		//糖果总数
		int count=n;
		for(int i=0;i<n-1;i++) {
			if(ratings[i]>ratings[i+1]) {
				if(a[i]==0)a[i]+=1;
				int temp=i;
				//遍历前面的数，比自身大的都递增1
				while(temp>=1) {
					if(ratings[temp]<ratings[temp-1] && a[temp]>=a[temp-1]) {
						a[temp-1]=a[temp]+1;
					}
					temp--;
				}
			}else if(ratings[i]<ratings[i+1]){
				a[i+1]=a[i]+1;
			}
		}
		for(int i:a) {
			System.out.print(i+",");
			count+=i;
		}
		System.out.println("");
		return count;
	}
	//两次遍历
	/**
	 * 一个从左向右遍历，递增的都+1，递减的=1
	 * 一个从右向左遍历，递增的都=1，递减的+1
	 * 最后对比两个数组，去除最大的数字然后相加
	 * */
	public int candy2(int[] ratings) {
	    int n = ratings.length;
	    int[] left = new int[n];
	    for (int i = 0; i < n; i++) {
	        if (i > 0 && ratings[i] > ratings[i - 1]) {
	            left[i] = left[i - 1] + 1;
	        } else {
	            left[i] = 1;
	        }
	    }
	    int right = 0, count = 0;
	    for (int i = n - 1; i >= 0; i--) {
	        if (i < n - 1 && ratings[i] > ratings[i + 1]) {
	            right++;
	        } else {
	            right = 1;
	        }
	        System.out.print("left:"+left[i]+",,,");
	        System.out.println("right:"+right);
	        count += Math.max(left[i], right);
	    }
	    return count;
	}
	//常数空间遍历
	/**
	 * 根据评分的递增则后一位比前一位+1，
	 * 根据评分的递减则递减数量开始+1，如果遇到与递增数量相同则再+1，直到递减结束
	 * */
	public int candy3(int[] ratings) {
        int n = ratings.length;
        int count = 1;
        int inc = 1, dec = 0, pre = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] >= ratings[i - 1]) {
                dec = 0;
                pre = ratings[i] == ratings[i - 1] ? 1 : pre + 1;
                count += pre;
                inc = pre;
            } else {
                dec++;
                if (dec == inc) {
                    dec++;
                }
                count += dec;
                pre = 1;
            }
        }
        return count;
    }
}
